/*
 * live.cpp
 *
 *  Created on: Jul 22, 2010
 *      Author: vincent
 */

#include "ssa.h"
#include <algorithm>
#include <iterator>
#include <deque>

using namespace std;

dyn_bitset& bitsetOr(dyn_bitset& set1 , dyn_bitset& set2){
    assert(set1.size() == set2.size() && "operator on two different-sized set");

    transform(set1.begin(),set1.end(),  // source1 range
              set2.begin(),             // source2 range
              set1.begin(),             // dest range
              logical_or<bool>() );

    return set1;
}

dyn_bitset& bitsetAndNot(dyn_bitset& set1 , dyn_bitset& set2){
    assert(set1.size() == set2.size() && "operator on two different-sized set");

    // not every stl library has function compositor, so calculate in two steps
    dyn_bitset  tmpSet = dyn_bitset(set1.size(),false);
    transform(set2.begin(),set2.end(),tmpSet.begin(),logical_not<bool>());
    transform(tmpSet.begin(),tmpSet.end(),set1.begin(),set1.begin(),logical_and<bool>());

    return set1;
}

LiveNode::LiveNode(BasicBlock *bb,int size):AnalysisNode(bb){
    liveIn = new vector<bool>(size,false);
    gen = new vector<bool>(size,false);
    killed = new vector<bool>(size,false);
}

void LiveNode::define(int varIndex){
    if(varIndex < 0){
        return;
    }

    if(!(*gen)[varIndex]){
        //cout<<"define "<<varIndex<<endl;
        // defined before any usage
        (*killed)[varIndex] = true;
    }
}

void LiveNode::use(int varIndex){
    if(varIndex < 0){
        return;
    }

    if(!(*killed)[varIndex]){
        //cout<<"use "<<varIndex<<endl;
        // use before any definition
        (*gen)[varIndex] = true;
    }
}

LiveAnalysis::LiveAnalysis(CFG *cfg):Analysis<LiveNode>(cfg){
    localVarNum = cfg->getFunctionSymbol()->context->nextSlot;

    log.setDebug(false);
    log<<"localVarNum"<<localVarNum;

}

LiveNode* LiveAnalysis::createNode(BasicBlock* bb){
    return new LiveNode(bb,localVarNum);
}

void    LiveAnalysis::scan(BasicBlock *bb){
    BasicBlock::iterator it;
    LiveNode *node = getOrCreateNode(bb);
    Context *ctx = cfg->getFunctionSymbol()->context;

    log<<"scaning block"<<bb->getDfsNo();
    for(it = bb->begin();it != bb->end();it++){
        Opcode *o = *it;

        if(BinaryOpcode *op = dynamic_cast<BinaryOpcode*>(o)){
            node->use(ctx->regToVar(op->lhs));
            node->use(ctx->regToVar(op->rhs));
            node->define(ctx->regToVar(op->dst));
        }else if(MovOp *op = dynamic_cast<MovOp*>(o)){
            node->use(ctx->regToVar(op->src));
            node->define(ctx->regToVar(op->dst));
        }
    }
}

void    LiveAnalysis::scanBlocks(){
    CFG::iterator   it;

    for(it = cfg->begin();it != cfg->end();it++){
        scan(*it);
    }
}

void LiveAnalysis::buildLiveness(){
    CFG::dfs_reverse_iterator   it;
    deque<BasicBlock*>  workList;

    scanBlocks();

    // use post order, children's livein info are collected before processing
    // exclude the start block
    remove_copy_if(cfg->dfsRbegin(),cfg->dfsRend(),
            back_inserter(workList),
            bind2nd(equal_to<BasicBlock*>(),cfg->getStartBlock()));

    while(!workList.empty()){
        BasicBlock *bb = workList.front();
        workList.pop_front();

        dyn_bitset tmpSet(localVarNum,false);
        LiveNode *node = getOrCreateNode(bb);
        log<<"buildLiveness block"<<bb->getDfsNo()<<endl;

        for(BasicBlock::succ_iterator succ_it = bb->getSuccBegin();
            succ_it != bb->getSuccEnd();succ_it++){
            BasicBlock *sbb = *succ_it;
            LiveNode *snode = getOrCreateNode(sbb);
            bitsetOr(tmpSet,*snode->liveIn);
        }

        // now tmpSet is liveOut
        bitsetAndNot(tmpSet,*node->killed);
        bitsetOr(tmpSet,*node->gen);

        if(tmpSet != *node->liveIn){
            log<<"changed"<<endl;
            *node->liveIn = tmpSet;
            if(!count(workList.begin(),workList.end(),bb)){
                workList.push_back(bb);
            }
        }
    }
}

void LiveAnalysis::printBlocks(){
    CFG::dfs_iterator it;

    for(it = cfg->dfsBegin();it != cfg->dfsEnd();it++){
        BasicBlock *bb = *it;
        LiveNode *node = getOrCreateNode(bb);
        log<<"Block"<<bb->getDfsNo()<<": ";
        if(log.getDebug()){
            copy(node->liveIn->rbegin(),node->liveIn->rend(),ostream_iterator<bool>(log.getStream()));
        }
        log<<endl;
    }
}


